package main

//给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
//
//
//
// 示例 1：
//
//
//输入：nums = [1,1,2]
//输出：
//[[1,1,2],
// [1,2,1],
// [2,1,1]]
//
//
// 示例 2：
//
//
//输入：nums = [1,2,3]
//输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
//
//
//
//
// 提示：
//
//
// 1 <= nums.length <= 8
// -10 <= nums[i] <= 10
//
// Related Topics 数组 回溯 👍 973 👎 0

//leetcode submit region begin(Prohibit modification and deletion)
func permuteUnique(nums []int) (result [][]int) {
	// used[i][j]代表数字j是否在第i位被使用过，如果被使用过了，该位置就不能再选用该数字了，不然会出现重复
	// 由于-10 <= nums[i] <= 10，所以这里的0 <= j = nums[i] + 10 <= 20
	// 例如：求[1,2,1]的全排列，[2,1,1]只能出现一次，因为当第二位再选用原数组的第三位的1时，会因为used[1][11]为true
	used := make([][]bool, len(nums))
	for i, _ := range used {
		used[i] = make([]bool, 21)
	}
	pos := make([]bool, len(nums))
	var dfs func(ans []int)
	dfs = func(ans []int) {
		if len(ans) == len(nums) {
			tmp := make([]int, len(nums))
			copy(tmp, ans)
			result = append(result, tmp)
			return
		}
		for i := 0; i < len(nums); i++ {
			if !pos[i] && !used[len(ans)][nums[i]+10] {
				pos[i] = true
				used[len(ans)][nums[i]+10] = true
				dfs(append(ans, nums[i]))
				pos[i] = false
			}
		}
		for i := 0; i < len(used[len(ans)]); i++ {
			used[len(ans)][i] = false
		}
	}
	dfs([]int{})
	return result
}

//leetcode submit region end(Prohibit modification and deletion)
